On chromatic transversal domination in graphs

Title: On chromatic transversal domination in graphs
Creator: Arumugam, S.; Raja Chandrasekar, K.
Relation: Journal of Combinatorial Mathematics and Combinatorial Computing Vol. 83, p. 13-21
Relation: http://www.combinatorialmath.ca/jcmcc/jcmcc83.html
Publisher: Charles Babbage Research Centre
Resource Type: journal article
Date: 2012
Description: Let G = (V, E) be a graph with chromatic number k. A dominating set D of G is called a chromatic transversal dominating set (ctdset) if D intersects every color class of any k-coloring of G. The minimum cardinality of a ctd-set of G is called the chromatic transversal domination number of G and is denoted by γct(G). In this paper we obtain sharp upper and lower bounds for γct for the Mycielskian μ(G) and the shadow graph Sh(G) of any graph G. We also prove that for any c ≥ 2, the decision problem corresponding to 7ct is NP-hard for graphs with x(G) = c.
Subject: domination; coloring; chromatic transversal domination
Identifier: http://hdl.handle.net/1959.13/1336000
Identifier: uon:27527
Identifier: ISSN:0835-3026
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format